1. Field of the Invention
The present invention generally relates to computer hardware and, more specifically, to methods and systems that avoid deadlocks by marking CPU traffic as special.
2. Description of the Related Art
A conventional computer system includes a central processing unit (CPU) and may also include a co-processor known as a parallel processing unit (PPU). The CPU offloads certain processing operations to the PPU to reduce the processing workload of the CPU. These processing operations include, among others, compression and decompression operations. The CPU issues requests to the PPU, including read requests and/or write requests, when the CPU requires these processing operations. For example, the CPU may need to write data to system memory that might be stored in a compressed format. The CPU transmits a write request to the PPU, and the PPU may then read and decompress data associated with the write request and write the original data, decompressed and merged with the new data, to the system memory.
At times, a write request issued by the CPU may cause the PPU to issue one or more “derivative” read requests that must be completed before the initial write request can complete. For example, the PPU may issue a derivative read request that targets a system memory unit associated with the CPU. When the read transaction is completed, the system memory issues a read completion to the PPU that notifies the PPU that the transaction is complete.
Problems may arise, however, when the CPU and the PPU are connected by a peripheral component interface express (PCIe) bus that has one or more pending write requests. Due to the ordering rules of the PCIe bus, read completions cannot pass write requests, and so any derivative read requests cannot return read completions to the PPU. Thus, the initial write request cannot complete. This situation is known in the art as a circular dependency, or “deadlock.” A deadlock halts some or all communication between the CPU and the PPU and negatively affects the processing throughput of the computer system. Some examples of deadlock conditions are discussed below.
In a first example, a deadlock may occur if the PPU needs to read from a page table stored in system memory and write requests are pending in the PCIe bus. When the PPU issues a read request to system memory to retrieve an entry from the page table, a read completion associated with the read request cannot return to the PPU, and so the initial write request cannot complete.
A deadlock may also occur when the CPU issues a write request to the PPU that targets a cache line in a cache memory unit associated with the PPU. In order to complete the write request, the PPU first determines whether the cache line is compressed by examining a tag store. The tag store indicates a compression status associated with recently accessed cache lines in the cache memory unit. When the tag store does not include the compressions status of the cache line specified by the write request, the PPU issues a read request to system memory to access a backing store that includes the compression status of each cache line in the cache memory unit. The backing store returns the compression status of the specified cache line and issues a read completion. However, a deadlock may occur when write requests are pending in the PCIe because the read completion associated with the read request cannot pass these pending write requests.
A third deadlock may occur when the CPU attempts to write data to a region of system memory that is compressed, known in the art as a “compression tile.” The CPU issues a write request to the PPU that specifies the compression tile and includes the write data. The PPU issues a read request to system memory to read the compression tile. A deadlock may occur when write requests are pending in the PCIe because, again, a read completion associated with the read request cannot pass these pending write requests.
In addition to these three examples, numerous other circumstances may cause a deadlock. Accordingly, there remains a need in the art for methods and systems that avoid deadlocks.